package simple.tree;

import struct.TreeNode;

import java.util.*;

/**
 * 144. 二叉树的前序遍历
 * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 * 示例 1：
 *   输入：root = [1,null,2,3]
 *   输出：[1,2,3]
 * 示例 2：
 *   输入：root = []
 *   输出：[]
 * 示例 3：
 *   输入：root = [1]
 *   输出：[1]
 * 示例 4：
 *   输入：root = [1,2]
 *   输出：[1,2]
 * 示例 5：
 *   输入：root = [1,null,2]
 *   输出：[1,2]
 * 提示：
 *   树中节点数目在范围 [0, 100] 内
 *   -100 <= Node.val <= 100
 * @author 刘学松
 * @date 2021-12-26 2:56
 */
public class 二叉树的前序遍历 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        preorder(list, root);
        return list;
    }

    public void preorder(List<Integer> list, TreeNode node) {
        if (node != null) {
            list.add(node.val);
            preorder(list, node.left);
            preorder(list, node.right);
        }
    }

    public List<Integer> iterator(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        TreeNode node = root;
        while (!queue.isEmpty() || node != null) {
            while (node != null) {
                // 往头部插入
                queue.push(node);
                list.add(node.val);
                node = node.left;
            }
            // 弹出头部
            node = queue.pop().right;
        }
        return list;
    }
}
